import Nat "mo:base/Nat";
import Array "mo:base/Array";
// import Debug "mo:base/Debug";

actor {
  func fib(n:Nat):Nat{
    if (n<=1){
       1
    }else{
       fib(n-1)+ fib(n-2)
    }
  };

  public func fibonacci(n : Nat) : async Text {
    "fib(" # Nat.toText(n) # ")=" # Nat.toText(fib(n))  
  };


  func quickSort(arr:[Int]):[Int]{
    var newArr:[var Int] = Array.thaw(arr);
    Paritition(newArr,0,newArr.size()-1);
    Array.freeze(newArr)
  };

  func Paritition(arr:[var Int], low:Nat, high:Nat){
  if(low>=high) return;
   var pivot = arr[low];
   var left=low;
   var right= high;
   while (left < right) {
     while (left < right and arr[right] >= pivot) {
       right -= 1;
     };
     arr[left] := arr[right];
     while (left < right and arr[left] <= pivot) {
       left += 1;
     };
     arr[right] := arr[left];
   };
   arr[right] := pivot;
   if (left >=1) Paritition(arr,low,left-1);
   Paritition(arr,left+1,high); //执行两次
   };
 };

public func qSort(arr:[Int]):async [Int]{
  quickSort(arr)
};


};
